A communication network includes a communication medium, such as a transmission cable, and a plurality of stations connected to the medium for communication. Each station comprises a communicating device, for example a processor, a mass storage devices, or an input and output terminal, and circuitry for interfacing the device to the medium. Communications on the medium follow a prescribed communication protocol. A protocol is a set of rules describing the circumstances under which a station may communicate on the medium, the format of the communications, the proper response to various eventualities that may occur during communications, and other matters that must be consistent from station to station in order for the various stations to be able to communicate with each other across the medium.
While many communication protocols exist, one type of protocol that has become popular in recent years is the so-called carrier sense multiple access with collision detection (CSMA/CD) protocol. A well-known example of a network based on the CSMA/CD scheme is the Ethernet.RTM. of Xerox Corporation. In a CSMA/CD network such as the Ethernet, the stations contend for use of the communication medium. A station is allowed to transmit on the medium only when it detects the medium to be quiescent, that is, idle. Because of signal propagation delays, it is possible for two or more stations to determine that the medium is quiescent and to start transmitting on the medium substantially simultaneously. These transmissions interfere with each other and become scrambled. This interference is referred to as a collision.
Because the transmissions become scrambled in a collision, retransmission of collided communications is necessary. To minimize the possibility of their transmissions colliding again, the stations must attempt to stagger in time their retransmissions. For this purpose, each station in the network follows a predetermined formula for determining how long it must delay following the occurrence of a collision before reattempting a transmission of a collided communication. The delay time is referred to as a backoff period. Timing of the backoff period is conventionally commenced when a station terminates a collision-producing transmission.
The formula for computing the backoff period uses a random number multiple of a basic delay time period, referred to as a time slot, to determine the backoff period. The time slot is at least equal in duration to the network's to the collision window, which is the maximum time period during which any transmission is in danger of possibly colliding with another transmission. To stagger the stations' retransmissions, the random number is independently generated at each station, and hence the backoff period generally varies from station to station. And to avoid giving any station preferential access to the medium, a new random number is generated at each station following each collision, and hence the backoff period generally varies at each station from collision to collision. Nevertheless, the formula leads to an average period of time following a collision during which period no station will attempt to retransmit a collided communication.
The time during which no station is transmitting and the medium is quiescent is wasted time, overhead, from the viewpoint of network performance. The overhead adversely affects network communication throughput: the greater the overhead, the lower the maximum network capacity per unit of time. Therefore, to maximize network throughput, it is desirable to minimize the average retransmission delay time following a collision. And since the delay time is a product of the time slot, a shortening of the time slot yields a shorter average delay time.
However, the time slot is a function of transmission propagation delays, which are determined by the physical parameters of the network. In particular, the time slot, S, has conventionally been computed as EQU S.gtoreq.2B+2A
where A is the maximum interstation transmission propagation delay on the medium, and where B is the intrastation propagation delay. B is defined as the time period from the point at which one station initiates a transmission to the point at which another station can avoid initiating a transmission in response to sensing the transmission of the one station, assuming zero interstation transmission propagation delay on the medium. These propagation delays are inherent in the network and hence immutable for that network. Therefore the minimum time slot, as conventionally determined, is presently immutable for a given network, and minimization of the average transmission delay time is constrained thereby.